﻿#include <iostream>
#include<algorithm>
#include<vector>
#include <time.h>
using namespace std;

struct mynode {
    int index;
    int finished_t;//不考虑输入的，本地时间为0传输时间为1的理想情况下的完成时间 也就是子节点个数
    double true_finished_t;
    vector<mynode>childs;
    mynode(int i):index(i),finished_t(0), true_finished_t(0){}
    mynode(int i,int j) :index(i), finished_t(j), true_finished_t(0) {}
};
class algorithm_test {
public:
    double cost_compute(vector<int>&father,vector<vector<int>>&son,vector<vector<double>>&trans_time, vector<double>&local_time) {
        int N = father.size();
        vector<double>finished_time(N,-1);
        vector<int>unfinished(N);
        for (int i = 0; i < N; ++i) {
            unfinished[i] = i;
        }
        //找到root
        int root = 0;
        auto it = father.begin();
        while (it != father.end()) {
            if (*it == -1) {
                break;
            }
            ++root;
            ++it;
        }
        //开始由下往上计算用时
        while (finished_time[root]==-1) {
            //找到所有子节点都已经有完成时间的节点
            auto it_unfinished = unfinished.begin();
            while (it_unfinished != unfinished.end()) {
                int i = *it_unfinished;
                bool flag_can_be_finished = true;//可以被计算完成时间
                for (int j = 0; j < son[i].size(); ++j) {
                    if (finished_time[son[i][j]] == -1)
                    {
                        flag_can_be_finished = false;
                        break;
                    }
                }
                if (flag_can_be_finished) {//计算该节点的完成时间
                    it_unfinished=unfinished.erase(it_unfinished);
                    int n_son = son[i].size();
                    if (n_son == 0) {
                        finished_time[i] = local_time[i];
                        continue;
                    }
                    vector<pair<double, int>>temp_pair;
                    for (int j = 0; j < n_son; ++j) {
                        temp_pair.push_back(make_pair(finished_time[son[i][j]], son[i][j]));
                    }
                    sort(temp_pair.begin(), temp_pair.end());//将子节点根据完成时间由小到大排序
                    finished_time[i] = local_time[i];//用本地训练时间初始化
                    for (int j = 0; j < n_son; ++j) {
                        if (finished_time[i] >= temp_pair[j].first) {   //父节点完成时子节点已经可以开始传输了 直接加传输的时间
                            finished_time[i] += trans_time[temp_pair[j].second][i];
                        }
                        else {//父节点等待子节点完成再开始传输 时间为子节点完成并传输的时间
                            finished_time[i] = temp_pair[j].first + trans_time[temp_pair[j].second][i];
                        }
                    }
                }
                else {
                    ++it_unfinished;
                }
            }
        }
        return finished_time[root];
    }
    //传输时间最短节点（次优）
    mynode topology_strategy(vector<vector<double>>& trans_time, vector<double>& local_time) {
        int n = local_time.size();
        int m=1;
        while ((n-1) >> m != 0) { ++m;}//使得2^(m-1)<n<=2^m
        //获取最优结构
        int cut_n = (1<<m) - n;
        vector<int>saturation_m(m+1);//完成时间为m的饱和结构包含各个完成时间的个数，饱和时间范围为0~m-1
        saturation_m[m] = 1;//完成时间为m的只有一个
        for (int i = 0; i < m; ++i) {
            saturation_m[i] = 1<<(m-i-1);
        }
        for (int i = 0; i < m - 1;++i) {
            if ((cut_n >> i) & 1) {//摘掉一个饱和度为i的子树
                --saturation_m[i];
                for (int j = 0; j < i; ++j) {
                    saturation_m[j] -= 1<<(i-j-1);
                }
            }
        }
        //对本地处理时间进行排序
        vector<pair<double, int>>local_time_pair;
        for (int i = 0; i < n;++i) {
            local_time_pair.push_back(make_pair(local_time[i],i));
        }
        sort(local_time_pair.begin(), local_time_pair.end());
        //开始构建树结构
        vector<vector<mynode>>trees(m + 1);//完成时间为索引的树
        for (int i = 0; i < m+1; ++i) {//从完成时间为0的节点开始构建
            for (int j = 0; j < saturation_m[i]; ++j) {//需要构建saturation_m[i]个完成时间为i的树  这里有一些实现细节还可以调整
                auto root = local_time_pair.begin();//用本地最快的节点当根节点
                int root_i = (*root).second;
                local_time_pair.erase(root);
                mynode root_node(root_i,i);//新建节点，再添加子节点
                for (int k = 0; k < i; ++k) {//完成时间0到i-1的子节点各一个 
                    int temp_index=-1;//传输时间最短节点在trees中的索引
                    double temp_min = 1e6;
                    if (trees[k].size() == 0)//最后一层可能有一些节点被剪掉了
                        continue;
                    for (int h = 0; h < trees[k].size(); ++h) {//找到完成时间为k的树中到节点root_i传输时间最短的 作为子节点
                        if (trans_time[trees[k][h].index][root_i] < temp_min) {
                            temp_min = trans_time[trees[k][h].index][root_i];
                            temp_index = h;
                        }
                    }
                    root_node.childs.push_back(trees[k][temp_index]);
                    auto it = trees[k].begin();//移除该节点
                    while (temp_index > 0) {
                        ++it;
                        --temp_index;
                    }
                    trees[k].erase(it);
                }
                trees[i].push_back(root_node);
            }
        }
        
        return trees[m][0];
    }
    pair<vector<int>, vector<vector<int>>>tree2adj(mynode& root,int n ) {//将树结构转化为邻接矩阵
        vector<int> father(n,-1);
        vector<vector<int>>son(n);
        DFS(father,son,root);
        return make_pair(father, son);
    }
    void DFS(vector<int>& father, vector<vector<int>>& son,mynode& root) {
        for (auto& it : root.childs) {
            father[it.index] = root.index;
            son[root.index].push_back(it.index);
            DFS(father,son,it);
        }
    }
    pair<vector<vector<double>>, vector<double>>random_input(int n){
        vector<double>local_time(n);
        vector<vector<double>>trans_time(n, vector<double>(n));
        for (int i = 0; i < n; ++i) {
            local_time[i] = Random(10,50);
            for (int j=0; j< n; ++j) {
                trans_time[i][j] = Random(5,30);
            }
        }
        return make_pair(trans_time, local_time);
    }
    double Random(double start, double end) {
        double dis = end - start;
        return start + dis * (rand() / double(RAND_MAX));
    }

    void cost_compute(mynode& root, const vector<vector<double>>& trans_time, const vector<double>& local_time) {

        vector<pair<double, int>>temp_pair;
        for (int j = 0; j < root.childs.size(); ++j) {
            temp_pair.push_back(make_pair(root.childs[j].true_finished_t, root.childs[j].index));
        }
        sort(temp_pair.begin(), temp_pair.end());//将子节点根据完成时间由小到大排序
        root.true_finished_t = local_time[root.index];//用本地训练时间初始化
        for (int j = 0; j < root.childs.size(); ++j) {
            if (root.true_finished_t >= temp_pair[j].first) {   //父节点完成时子节点已经可以开始传输了 直接加传输的时间
                root.true_finished_t += trans_time[temp_pair[j].second][root.index];
            }
            else {//父节点等待子节点完成再开始传输 时间为子节点完成并传输的时间
                root.true_finished_t = temp_pair[j].first + trans_time[temp_pair[j].second][root.index];
            }
        }

    }
    //完成时间最短节点（最优）
    mynode topology_strategy2(vector<vector<double>>& trans_time, vector<double>& local_time) {
        int n = local_time.size();
        int m = 1;
        while ((n - 1) >> m != 0) { ++m; }//使得2^(m-1)<n<=2^m
        //获取最优结构
        int cut_n = (1 << m) - n;
        vector<int>saturation_m(m + 1);//完成时间为m的饱和结构包含各个完成时间的个数，饱和时间范围为0~m-1
        saturation_m[m] = 1;//完成时间为m的只有一个
        for (int i = 0; i < m; ++i) {
            saturation_m[i] = 1 << (m - i - 1);
        }
        for (int i = 0; i < m - 1; ++i) {
            if ((cut_n >> i) & 1) {//摘掉一个饱和度为i的子树
                --saturation_m[i];
                for (int j = 0; j < i; ++j) {
                    saturation_m[j] -= 1 << (i - j - 1);
                }
            }
        }
        //对本地处理时间进行排序
        vector<pair<double, int>>local_time_pair;
        for (int i = 0; i < n; ++i) {
            local_time_pair.push_back(make_pair(local_time[i], i));
        }
        sort(local_time_pair.begin(), local_time_pair.end());
        //开始构建树结构
        vector<vector<mynode>>trees(m + 1);//完成时间为索引的树
        for (int i = 0; i < m+1; ++i) {//从完成时间为0的节点开始构建
            for (int j = 0; j < saturation_m[i]; ++j) {//需要构建saturation_m[i]个完成时间为i的树  这里有一些实现细节还可以调整
                auto root = local_time_pair.begin();//用本地最快的节点当根节点
                int root_i = (*root).second;
                local_time_pair.erase(root);
                mynode root_node(root_i, i);//新建节点，再添加子节点
                for (int k = 0; k < i; ++k) {//完成时间0到i-1的子节点各一个 
                    if (trees[k].size() == 0)//最后一层可能有一些节点被剪掉了
                        continue;
                    int temp_index = -1;//完成时间最短节点在trees中的索引
                    double temp_min = 1e6;
                    cost_compute(root_node, trans_time, local_time);//计算当前已有子节点的情况下 根节点完成时间
                    for (int h = 0; h < trees[k].size(); ++h) {//找到作为子节点后新的完成时间最小的
                        if (root_node.true_finished_t >= trees[k][h].true_finished_t) {
                            if(root_node.true_finished_t + trans_time[trees[k][h].index][root_i]< temp_min){
                                temp_min= root_node.true_finished_t + trans_time[trees[k][h].index][root_i];
                                temp_index = h;
                            }
                        }
                        else {
                            if (trees[k][h].true_finished_t + trans_time[trees[k][h].index][root_i] < temp_min) {
                                temp_min = trees[k][h].true_finished_t + trans_time[trees[k][h].index][root_i];
                                temp_index = h;
                            }
                        }
                    }
                    root_node.childs.push_back(trees[k][temp_index]);
                    auto it = trees[k].begin();//移除选中的节点
                    while (temp_index > 0) {
                        ++it;
                        --temp_index;
                    }
                    trees[k].erase(it);
                }
                //计算新节点的真实完成时间
                cost_compute(root_node,trans_time,local_time);
                trees[i].push_back(root_node);
            }
        }
        return trees[m][0];
    }
    mynode topology_fixed(int n) {//用来对比的 固定的一个饱和结构
        int m = 1;
        while ((n - 1) >> m != 0) { ++m; }//使得2^(m-1)<n<=2^m
        //获取最优结构
        int cut_n = (1 << m) - n;
        vector<int>saturation_m(m + 1);//完成时间为m的饱和结构包含各个完成时间的个数，饱和时间范围为0~m-1
        saturation_m[m] = 1;//完成时间为m的只有一个
        for (int i = 0; i < m; ++i) {
            saturation_m[i] = 1 << (m - i - 1);
        }
        for (int i = 0; i < m - 1; ++i) {
            if ((cut_n >> i) & 1) {//摘掉一个饱和度为i的子树
                --saturation_m[i];
                for (int j = 0; j < i; ++j) {
                    saturation_m[j] -= 1 << (i - j - 1);
                }
            }
        }
        vector<int>unused;
        for (int i = 0; i < n; ++i) {
            unused.push_back(i);
        }
        //开始构建树结构
        vector<vector<mynode>>trees(m + 1);
        for (int i = 0; i < m + 1; ++i) {
            for (int j = 0; j < saturation_m[i]; ++j) {
                auto root = unused.begin();
                int root_i = *root;
                unused.erase(root);
                mynode root_node(root_i, i);
                for (int k = 0; k < i; ++k) {
                    if (trees[k].size() == 0)//最后一层可能有一些节点被剪掉了
                        continue;
                    root_node.childs.push_back(trees[k][0]);
                    auto it = trees[k].begin();
                    trees[k].erase(it);
                }
                trees[i].push_back(root_node);
            }
        }
        return trees[m][0];
    }
    mynode topology_fixed2(int n) {//用来对比的 固定的一个星型结构
        mynode root(0);
        for (int i = 1; i < n; ++i) {
            root.childs.push_back(mynode(i));
        }
        return root;
    }
    pair<vector<int>, vector<vector<int>>> topology_fixed3(int n) {//用来对比的 二叉树结构 直接输出邻接表
        vector<int> father(n, -1);
        vector<vector<int>>son(n);
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                father[i] = (i-1) / 2;
            }
            if (2 * i + 1 < n) {
                son[i].push_back(2 * i + 1);
            }
            if (2 * i + 2 < n) {
                son[i].push_back(2 * i + 2);
            }
        }
        return make_pair(father, son);
    }
    mynode topology_strategy2_log(vector<vector<double>>& trans_time, vector<double>& local_time) {//跟topology_strategy2一样，只是为了输出中间数据，写专利的实例时用的
        int n = local_time.size();
        int m = 1;
        while ((n - 1) >> m != 0) { ++m; }//使得2^(m-1)<n<=2^m
        //获取最优结构
        int cut_n = (1 << m) - n;
        vector<int>saturation_m(m + 1);//完成时间为m的饱和结构包含各个完成时间的个数，饱和时间范围为0~m-1
        saturation_m[m] = 1;//完成时间为m的只有一个
        for (int i = 0; i < m; ++i) {
            saturation_m[i] = 1 << (m - i - 1);
        }
        for (int i = 0; i < m - 1; ++i) {
            if ((cut_n >> i) & 1) {//摘掉一个饱和度为i的子树
                --saturation_m[i];
                for (int j = 0; j < i; ++j) {
                    saturation_m[j] -= 1 << (i - j - 1);
                }
            }
        }

        cout << "saturation_m:" << endl;
        cout << "[";
        for (auto it = saturation_m.begin(); it != saturation_m.end(); ++it) {
            cout << *it;
            if (it != saturation_m.end() - 1)
                cout << ",";
        }
        cout << "]" << endl;


        //对本地处理时间进行排序
        vector<pair<double, int>>local_time_pair;
        for (int i = 0; i < n; ++i) {
            local_time_pair.push_back(make_pair(local_time[i], i));
        }
        sort(local_time_pair.begin(), local_time_pair.end());

        cout << "排序结果:" << endl;
        for (auto& it : local_time_pair) {
            cout << it.second << " ";
        }
        cout << endl;




        //开始构建树结构
        vector<vector<mynode>>trees(m + 1);//完成时间为索引的树
        for (int i = 0; i < m + 1; ++i) {//从完成时间为0的节点开始构建
            cout <<"*************完成时间为"<<i<< endl;
            for (int j = 0; j < saturation_m[i]; ++j) {//需要构建saturation_m[i]个完成时间为i的树  这里有一些实现细节还可以调整
                auto root = local_time_pair.begin();//用本地最快的节点当根节点
                int root_i = (*root).second;
                local_time_pair.erase(root);
                mynode root_node(root_i, i);//新建节点，再添加子节点
                for (int k = 0; k < i; ++k) {//完成时间0到i-1的子节点各一个 
                    cout << "子节点完成时间为" << k << endl;
                    if (trees[k].size() == 0)//最后一层可能有一些节点被剪掉了
                        continue;
                    int temp_index = -1;//完成时间最短节点在trees中的索引
                    double temp_min = 1e6;
                    cost_compute(root_node, trans_time, local_time);//计算当前已有子节点的情况下 根节点完成时间
                    cout << "trees[k]有：";
                    for (auto& it : trees[k]) {
                        cout << it.index << " ";
                    }
                    cout << endl;

                    for (int h = 0; h < trees[k].size(); ++h) {//找到作为子节点后新的完成时间最小的
                        if (root_node.true_finished_t >= trees[k][h].true_finished_t) {
                            cout << "h=" << h << "加入后完成时间：" << root_node.true_finished_t + trans_time[trees[k][h].index][root_i] <<endl;
                            if (root_node.true_finished_t + trans_time[trees[k][h].index][root_i] < temp_min) {
                                temp_min = root_node.true_finished_t + trans_time[trees[k][h].index][root_i];
                                temp_index = h;
                            }
                        }
                        else {
                            cout << "k=" << k << "加入后完成时间：" << trees[k][h].true_finished_t + trans_time[trees[k][h].index][root_i] << endl;
                            if (trees[k][h].true_finished_t + trans_time[trees[k][h].index][root_i] < temp_min) {
                                temp_min = trees[k][h].true_finished_t + trans_time[trees[k][h].index][root_i];
                                temp_index = h;
                            }
                        }
                    }
                    cout << "选中的节点为：" << trees[k][temp_index].index << endl;
                    root_node.childs.push_back(trees[k][temp_index]);
                    auto it = trees[k].begin();//移除选中的节点
                    while (temp_index > 0) {
                        ++it;
                        --temp_index;
                    }
                    trees[k].erase(it);
                }
                //计算新节点的真实完成时间
                cost_compute(root_node, trans_time, local_time);
                trees[i].push_back(root_node);
            }
        }
        return trees[m][0];
    }
};


void test1() {//平均用时与节点个数的关系
    auto S = algorithm_test();
    srand(1617244950);
    int runrounds = 2000;
    vector<double> averange_time;
    vector<int> test_n;

    for (int i = 2; i < 70; ++i) {
        test_n.push_back(i);
    }
    for (auto& it : test_n) {
        cout << "\r" << it;
        double sums = 0;
        for (int i = 0; i < runrounds; ++i) {
            auto rp = S.random_input(it);
            auto trans_time = rp.first;
            auto local_time = rp.second;
            auto trees = S.topology_strategy2(trans_time, local_time);
            auto adj = S.tree2adj(trees, local_time.size());
            double ans = S.cost_compute(adj.first, adj.second, trans_time, local_time);
            sums += ans;
            //cout << ans << endl;
        }
        averange_time.push_back(sums / runrounds);
    }
    cout << "--------" << endl;
    for (auto& it : averange_time) {
        cout << it << ",";
    }
}

int test2()//固定二叉树结构测试
{
    auto S = algorithm_test();
    srand(1617244950);
    int runrounds = 2000;
    vector<double> averange_time;
    vector<int> test_n;


    for (int i = 2; i < 70; ++i) {
        test_n.push_back(i);
    }
    for (auto& it : test_n) {
        cout << "\r" << it;
        double sums = 0;
        auto adj = S.topology_fixed3(it);
        //auto adj = S.tree2adj(trees,it);

        for (int i = 0; i < runrounds; ++i) {
            auto rp = S.random_input(it);
            auto trans_time = rp.first;
            auto local_time = rp.second;

            double ans = S.cost_compute(adj.first, adj.second, trans_time, local_time);
            sums += ans;
            //cout << ans << endl;
        }
        averange_time.push_back(sums / runrounds);
    }
    cout << "--------" << endl;
    for (auto& it : averange_time) {
        cout << it << ",";
    }


    return 0;
}

int main() {//为了写专利的实例部分，以11个节点为例
   
    auto S = algorithm_test();
    srand(1617244950);
    auto rp = S.random_input(11);
    auto trans_time = rp.first;
    auto local_time = rp.second;

    cout << "trans_time:" << endl;
    cout << "[";
    for (auto it = trans_time.begin(); it != trans_time.end();++it) {
        cout << "[";
        for (auto it2 = (*it).begin(); it2 != (*it).end() ; ++it2) {
            cout << *it2;
            if (it2 != (*it).end() - 1)
                cout << ",";
        }
        cout << "]";
        if (it != trans_time.end() - 1)
            cout << ";";
    }
    cout << "]"<<endl;

    cout << "local_time:" << endl;
    cout << "[";
    for (auto it = local_time.begin(); it != local_time.end(); ++it) {
        cout << *it;
        if (it != local_time.end() - 1)
            cout << ",";
    }
    cout << "]" << endl;

    auto trees = S.topology_strategy2_log(trans_time, local_time);

    auto adj = S.tree2adj(trees, local_time.size());
    //double ans = S.cost_compute(adj.first, adj.second, trans_time, local_time);
    

    return 0;
}
